package com.second.app.algorithm;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author GYZ
 * @Date 2024/2/5
 * <pre>
 *     举例说明：{8, 7, 5, 4, 3}
 *     假设不是随机打乱顺序，而是完全反序
 *     这时候如果使用冒泡排序，我们关注下冒泡排序的效率：
 *         比较次数：比较哪个数更大  需要比较10次
 *         交换次数：交换两个数的位置使他们按顺序排列  需要交换10次
 *     把这2个步骤相加，一个包含5个元素的数组，最多需要20步。
 *      以此类推      一个包含10个元素的数组，最多需要90步。
 *      因此冒泡排序效率，用大O计法来描述，是O(N²)，如果数据量比较大的话，此算法是比较低的，随着数据量变多，其步数也剧增。
 *      因此O(N²)也被叫做二次时间
 *
 * </pre>
 */
public class SortingRun {
    public static void main(String[] args) {

        int[] arr = {8, 18, 100, 4, 36, 28};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));

        int[] arr1 = {40, 20, 70, 10, 38};
        chooseSort(arr1);
        System.out.println(Arrays.toString(arr1));

        int[] arr2 = {19, 8, 38, 11, 6};
        insertSort(arr2);
        System.out.println(Arrays.toString(arr2));

        // 快速排序

        int[] arr3 = {12, 5, 18, 10, 3, 2};
        quickSort(arr3, 0, arr3.length - 1);
        System.out.println(Arrays.toString(arr3));

    }

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] =temp;
                }
            }
        }
    }

    //[4,2,7,1,3] 选择排序
    public static void chooseSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int lowNumberIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[lowNumberIndex]) {
                    lowNumberIndex = j;
                }
            }
            if (lowNumberIndex != i) {
                int temp = arr[i];
                arr[i] = arr[lowNumberIndex];
                arr[lowNumberIndex] = temp;
            }
        }
    }


    //[4, 2, 7, 1, 3] 插入排序
    public static void insertSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 分区
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        // 选最后一个索引位置的元素作为 基准pivot=2
        int pivot = arr[high];
        // i=-1
        int i = low - 1;
        //{12, 5, 18, 10, 3, 2}
        for (int j = low; j <= high - 1; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }


    //快速排序[0,5,2,1,6,3]
    public static void quicklySort(int[] arr) {
        int n = arr.length;
        int key = arr[arr.length - 1];
        int leftIndex = 0;
        int rightIndex = n - 2;
        for (int i = 0; i < n - 1; i++) {
            if (leftIndex == rightIndex) {
                arr[arr.length - 1] = arr[leftIndex];
                arr[leftIndex] = key;
                break;
            }
            if (arr[leftIndex] < key) {
                leftIndex++;
                continue;
            }
            if (arr[rightIndex] > key) {
                rightIndex--;
                continue;
            }
            int temp1 = arr[leftIndex];
            int temp2 = arr[rightIndex];
            arr[leftIndex] = temp2;
            arr[rightIndex] = temp1;
            leftIndex++;
        }
    }
}

